import collections
from functools import reduce
from typing import *


class Solution:

    def minimumLengthEncoding(self, words: List[str]) -> int:

        class Node(dict):
            pass

        words.sort(key=lambda a: len(a), reverse=True)
        root = Node()
        for word in words:
            node = root
            for w in word[::-1]:
                if w not in node:
                    node[w] = Node()
                node = node[w]

        def f(node: Node, s):
            if len(node.keys()) == 0:
                return s
            ans = 0
            for k, v in node.items():
                ans += f(v, s + 1)
            return ans

        return f(root, 1)


class Solution:

    def minimumLengthEncoding(self, words: List[str]) -> int:
        words = list(set(words))  #remove duplicates
        #Trie is a nested dictionary with nodes created
        # when fetched entries are missing
        Trie = lambda: collections.defaultdict(Trie)
        trie = Trie()

        #reduce(..., S, trie) is trie[S[0]][S[1]][S[2]][...][S[S.length - 1]]
        nodes = [reduce(dict.__getitem__, word[::-1], trie) for word in words]

        #Add word to the answer if it's node has no neighbors
        return sum(
            len(word) + 1 for i, word in enumerate(words)
            if len(nodes[i]) == 0)


s = Solution()
print(s.minimumLengthEncoding(["time", "atime", "btime"]))
print(s.minimumLengthEncoding(["time", "me", "bell"]))
print(s.minimumLengthEncoding(["t"]))

Trie = lambda: collections.defaultdict(Trie)
print(type(Trie))